package pri.zjy.backTracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 子集
 * @date 2025/6/14 23:21
 */
public class Subsets_78 {

    public static void main(String[] args) {

        Subsets_78 subsets78 = new Subsets_78();
        int[] nums = {1, 2, 3};
        subsets78.subsets(nums).forEach(System.out::println);
    }

    /**
     * dmsxl
     * <p>
     * 思路：每一个树层的结果都要记录；而组合、分割、排列问题只收集叶子节点的结果。
     */
    List<List<Integer>> result2 = new ArrayList<>();// 存放符合条件结果的集合
    List<Integer> path2 = new ArrayList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets2(int[] nums) {
        subsetsHelper2(nums, 0);
        return result2;
    }

    private void subsetsHelper2(int[] nums, int startIndex){
        result2.add(new ArrayList<>(path2));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path2.add(nums[i]);
            subsetsHelper2(nums, i + 1);
            path2.remove(path2.size() - 1);
        }
    }

    /**
     * 个解：递归回溯
     * <p>
     * 思路：转换为普通组合问题，不过要考虑所有组合元素个数的情况，组合个数∈[0, nums.length]
     */
    public List<List<Integer>> ans = new ArrayList<>();
    public List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        // nums元素不重复，每个元素使用一次
        // 子集包括空集，子集相当于组合（不考虑顺序）
        // 类似组合问题，只不过要找出元素个数为0~nums.length的组合

        // 1.返回值void，入参：nums，ans，path，startIndex，subsetSize
        // subsetSize作为递归的入参，只不过它的更改是在最外层作为for循环的条件
        // 因为当作为递归的入参时，无法更新subsetSize
        // 2.递归终止条件
        // path.size() == subsetSize，则记录path，并结束本层递归
        // 3.搜索过程
        // 两层for循环
        // 第一层，控制subsetSize个数：[0, nums.length]
        // 第二层，就是组合问题的横向遍历
        // 第二层中，进行元素记录、向下递归、回溯

        // 找到所有元素个数的子集[0, nums.length]
        for (int i = 0; i <= nums.length; i++) {
            backtrack(nums, 0, i);
        }
        return ans;
    }

    public void backtrack(int[] nums, int startIndex, int subsetSize) {
        // 收集到指定subsetSize，则记录
        if (path.size() == subsetSize) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 横向遍历
        for (int i = startIndex; i < nums.length; i++) {
            // 记录
            path.add(nums[i]);

            // 向下递归
            // 为什么startIndex = i+1？——因为这里实际是找组合，当前元素获取后，下一层应该从该元素后面开始取值，避免出现重复的组合
            backtrack(nums, i + 1, subsetSize);

            // 回溯
            path.remove(path.size() - 1);
        }

    }

}
